/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/longest-palindromic-substring
   @Language: C++
   @Datetime: 19-03-18 15:57
   */

// Method DP, Time O(n^2), Space O(n^2), 252ms
class Solution {
public:
	/**
	 * @param s: input string
	 * @return: the longest palindromic substring
	 */
	string longestPalindrome(string &s) {
		// write your code here
		int len=s.length();
		vector<vector<bool> > dp(len,vector<bool>(len,false));
		int begin=0, end=0;
		for(int j=0; j<len; j++)
			for(int i=0; i<=j; i++){
				if ((j-i<=1 || dp[i+1][j-1]) && s[i]==s[j])
					dp[i][j] = true;
				if (dp[i][j] && j-i>end-begin)
					begin=i, end=j;
			}
		return s.substr(begin,end-begin+1);
	}
};

// Method Center Expand, Time O(n^2), Space(1), 50ms
class Solution {
public:
	/**
	 * @param s: input string
	 * @return: the longest palindromic substring
	 */
	string longestPalindrome(string &s) {
		// write your code here
		int len=s.length();
		int begin=0, end=0;
		for(int i=0; i<len; ++i){
			if (len-i<(end-begin)/2) break;
			int left=i, right=i;
			for(; right<len-1 && s[right]==s[right+1]; right++);
			for(; left>0 && right<len-1 && s[left-1]==s[right+1]; left--,right++);
			if (end-begin<right-left) begin=left,end=right;
		}
		return s.substr(begin,end-begin+1);
	}
};

// Method Manacher, Time(n), Space(n), 50ms
class Solution {
public:
	/**
	 * @param s: input string
	 * @return: the longest palindromic substring
	 */
	string longestPalindrome(string &s) {
		// write your code here
		string str(s.length()*2+2,'#');
		str[0]='$';
		for(int i=0; i<s.length(); str[i*2+2]=s[i++]);
		int mx=0, id=0, center=0, r=0;
		vector<int> dp(str.length(),0);
		for(int i=1; i<str.length(); ++i){
			dp[i] = mx>i ? min(dp[id*2-i],mx-i):1;
			for(; str[i-dp[i]]==str[i+dp[i]]; ++dp[i]);
			if (mx<i+dp[i]){
				mx=i+dp[i];
				id=i;
			}
			if(r<dp[i]){
				r=dp[i];
				center=i;
			}
		}
		return s.substr((center-r)/2, r-1);
	}
};
